#include

#include

#include

using namespace std;

const int MAXN = 6;

int n = 5;

double W = 100;

struct NodeType {
	
	double w;
	
	double v;
	
	double p;
	
	bool operator<(const NodeType& s) const {
		
		return p > s.p;
		
	}
	
};

NodeType A[MAXN] = {{0}, {10, 20}, {20, 30}, {30, 66}, {40, 40}, {50, 60}};

double V;

double x[MAXN] = {0};

void Knap() {
	
	V = 0;
	
	double weight = W;
	
	int i = 1;
	
	while (i < n && A[i].w <= weight) {
		
		x[i] = 1;
		
		weight -= A[i].w;
		
		V += A[i].v;
		
		i++;
		
	}
	
	if (i < n && weight > 0) {
		
		x[i] = weight / A[i].w;
		
		V += x[i] * A[i].v ;
		
	}
	
}

void dispA() {
	
	for (int i = 1; i <= n; i++) {
		
		cout << "物品 " << i << ": 重量=" << A[i].w << ", 价值=" << A[i].v << ", 单位重量价值=" << A[i].p << endl;
		
	}
	
}

int main() {
	
	cout << "求解过程" << endl;
	
	for (int i = 1; i < n; i++)
		
		A[i].p = A[i].v / A[i].w;
	
	
	
	cout << "(1)排序前" << endl;
	
	dispA();
	
	sort(A + 1, A + n + 1);
	
	cout << "(2)排序后" << endl;
	
	dispA();
	
	Knap();
	
	cout << "(3)求解结果" << endl;
	
	cout << "x:[";
	
	for (int j = 1; j <= n; j++)
		
		cout << x[j] << ",";
	
	cout << "]" << endl;
	
	cout << "总价值=" << V << endl;
	
	return 0;
	
}
